class Solution {
    const int mod = 1e9+7;
    int res = 0;
public:  
    void merge(vector<int>& nums, vector<int>& tmp, int l, int mid, int r) {
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r) {
            if (nums[i] > nums[j]) {
                tmp[k++] = nums[j++];
                res += (mid - i + 1);
                res %= mod;
            } else {
                tmp[k++] = nums[i++];
            }
        }
        while (i <= mid) tmp[k++] = nums[i++];
        while (j <= r) tmp[k++] = nums[j++];

        for (k = 0, i = l; i <= r; k++, i++) {
            nums[i] = tmp[k];
        }
    }

    void mergeSort(vector<int>& nums, vector<int>& tmp, int l, int r) {
        if (l >= r) return;
        int mid = l + (r - l) / 2;
        mergeSort(nums, tmp, l, mid);
        mergeSort(nums, tmp, mid + 1, r);
        merge(nums, tmp, l, mid, r);
    }
    
    int InversePairs(vector<int>& nums) {
        vector<int> tmp(nums.size());
        mergeSort(nums, tmp, 0, nums.size() - 1);
        return res;
    }
};